8.4.3 פונקציות גיבוב

מבנה נתונים ואלגוריתמים

 

 

בחירת פונקצית גיבוב h(k) טובה, הינה חיונית עבור טבלאות גיבוב המבוססות על חיפוש. h חייבת לחלק את הפריטים שבאוסף בצורה אחידה ככל האפשר לתוך תאי טבלת הגיבוב. הקריטריון העיקרי הוא שיהיה מספר מינימלי של התנגשויות.

 

אם ההסתברות שמפתח k מופיע באוסף הפריטים הוא P(k), אזי אם ישנם m תאים בטבלה הגיבוב, פונקצית פיזור אחיד h(k) חייבת להבטיח כי:

 

 

 

לעיתים קל להבטיח דבר זה. לדוגמא, אם המפתחות מחולקים באופן אקראי ב- [r,0), אזי

h(k)=floor((mk)/r), יאפשר פיזור אחיד.

 

 

מיפוי מפתחות אל מספרים טבעיים

רוב פונקציות הגיבוב ממפות תחילה את המפתחות אל מספר סדרות של מספריםטבעיים כגון [r,0). ישנן דרכים רבות לבצע זאת. לדוגמא, אם המפתח הוא מחרוזת של תווי ASCII, ניתן פשוט לחבר את ייצוגי ה- ASCII של התווים במודולו (mod) 255 על מנת לקבל מספר בטווח (0,255), או שניתן לבצע על הערכים פעולת xor, או לחבר אותם בזוגות במודולו 1- 2¹⁶וכדומה.

 

מיפוי המפתחות לסדרה של מספרים טבעיים נותן מספר אפשרויות:

 

1.      שימוש בפונקצית מודולו (mod):

       h(k)=k mod m.

     כאשר משתמשים בשיטה זו, נמנעים בדרך כלל מערכים מסוימים של m. חזקות מסדר שני נמנעות בדרך כלל, עבור פונקצית

k mod 2^b       . פשוט נבחרות b הסיביות מהסדר הנמוך ביותר של k. פונקציה זו יעילה רק ידוע כי כל  2^bהערכים האפשריים

      של הסיביות מהסדר הנמוך ביותר סבירים באותה מידה, וזאת מאחר שמספר סיביות של המפתח אינן בשימוש בפונקצית

     הגיבוב.

 

     מספרים ראשוניים הקרובים לחזקות מסדר שני הם בדרך כלל בחירה טובה עבור m. לדוגמא, אם ישנם 4000 פריטים,

     ובחרנו בשיטת ארגון של טבלת גלישה, אך במקביל אנו מעונינים בסבירות נמוכה להתנגשויות, אזי נבחר 4093=m (4093

     הוא המספר הראשוני הגדול ביותר לפני 4096 = 2¹²).

 

2.      שימוש בשיטת ההכפלה:

·        הכפלת המפתח בקבוע A, 1>A>0.

·         חילוץ החלק של השבר מהתוצאה.

·         הכפלת הערך שהתקבל ב- m.

 

     לכן פונקציה הגיבוב תהיה:

h(k)=floor(m*(kA-floor(kA)))

 

    במקרה זה הערך של m לא קריטי ולרוב בוחרים חזקה מסדר 2, כך שניתן לקבל את ההליך היעיל הבא ברוב המחשבים:

·        בחירת m=2^p

·         הכפלת  w הסיביות של k ב- floor (A*2^w) על מנת לקבל תוצאה בעלת 2w סיביות.

·        לקיחת p הסיביות המשמעותיות ביותר של החצי התחתון של התוצאה.

 

הדבר נראה כך:

A=(sqrt(5)-1)2=0.6180339887

זוהי בחירה טובה.

 

3.      שימוש בגיבוב אוניברסלי:

      יריב אכזר יכול תמיד לבחור את המפתחות כך שכולם מגובבים לאותו תא בטבלה, ולגרום בכך לזמן שליפה ממוצע של O(n).     

      מטרתו של גיבוב אוניברסלי היא למנוע זאת על ידי בחירת פונקצית הגיבוב באופן אקראי, מתוך מבחר של פונקציות גיבוב.

      דרך זו מקטינה את הסבירות שפונקצית הגיבוב תפיק תוצאות גרועות, וגורמת לממוצע ביצוע טוב.

 

 

מושגים

 

גיבוב אוניברסלי

שיטה של בחירת פונקצית גיבוב באופן אקראית, בכדי ממוצע ביצוע טוב.

 

 

המשך ל: אלגוריתמים דינאמיים                     חזור ל: תוכן עניינים